package com.sheng.leetcode.year2022.swordfingeroffer.day31;

import org.junit.Test;

/**
 * @author liusheng
 * @date 2022/09/29
 *<p>
 * 剑指 Offer 43. 1～n 整数中 1 出现的次数<p>
 *<p>
 * 输入一个整数 n ，求1～n这n个整数的十进制表示中1出现的次数。<p>
 * 例如，输入12，1～12这些整数中包含1 的数字有1、10、11和12，1一共出现了5次。<p>
 *<p>
 * 示例 1：<p>
 * 输入：n = 12<p>
 * 输出：5<p>
 *<p>
 * 示例 2：<p>
 * 输入：n = 13<p>
 * 输出：6<p>
 *<p>
 * 限制：<p>
 * 1 <= n <2^31<p>
 * 注意：本题与主站 233 题相同：<a href="https://leetcode-cn.com/problems/number-of-digit-one/">...</a><p>
 *<p>
 * 来源：力扣（LeetCode）<p>
 * 链接：<a href="https://leetcode.cn/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof">...</a><p>
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。<p>
 */
public class Sword0043 {

    @Test
    public void test01() {
//        int n = 12;
        int n = 13;
        System.out.println(new Solution43().countDigitOne(n));
    }
}
class Solution43 {
    public int countDigitOne(int n) {
        /**
         * 个位数上出现1的个数：
         * (n / 10) * 1 + (n % 10 >= 1 ? 1 : 0)
         * 十位数上出现1的个数：
         * k = n % 10
         * (n / 100) * 10 + (if (k < 10) 0 else if (k > 19) 10 else (k - 10 + 1))
         */
        int count = 0;
        long k = 1;
        while (n >= k) {
            // 套用公式
            count += (n / (k * 10)) * k + Math.min(Math.max(n % (k * 10) - k + 1, 0), k);
            k *= 10;
        }
        return count;
    }
}
